
// 打家劫舍二
class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            return max(nums[0] + rob1(nums,2,n-2),rob1(nums,1,n-1));
        }
    
        int rob1(vector<int>& nums,int left,int right)
        {
            if(left > right) return 0;
            int n = nums.size();
            vector<int> T(n);
            vector<int> DT(n);
            T[left] = nums[left];
            for(int i = left + 1; i <= right; i++)
            {
                T[i] = DT[i-1] + nums[i];
                DT[i] = max(T[i-1],DT[i-1]);
            }
            return max(T[right],DT[right]);
        }
    };